{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Watch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: readBinaryWatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制手表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二进制手表顶部有 4 个 LED 代表<strong> 小时（0-11）</strong>，底部的 6 个 LED 代表<strong> 分钟（0-59）</strong>。每个 LED 代表一个 0 或 1，最低位在右侧。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，下面的二进制手表读取 <code>\"4:51\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/08/binarywatch.jpg\" style=\"height: 300px; width\" /></p>\n",
    "\n",
    "<p>给你一个整数 <code>turnedOn</code> ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 <strong>按任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>小时不会以零开头：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"01:00\"</code> 是无效的时间，正确的写法应该是 <code>\"1:00\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>分钟必须由两位数组成，可能会以零开头：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"10:2\"</code> 是无效的时间，正确的写法应该是 <code>\"10:02\"</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>turnedOn = 1\n",
    "<strong>输出：</strong>[\"0:01\",\"0:02\",\"0:04\",\"0:08\",\"0:16\",\"0:32\",\"1:00\",\"2:00\",\"4:00\",\"8:00\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>turnedOn = 9\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= turnedOn &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-watch](https://leetcode.cn/problems/binary-watch/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-watch](https://leetcode.cn/problems/binary-watch/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "\n",
    "        ans = []\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\")+bin(m).count(\"1\") == turnedOn:\n",
    "                    # ans.append(str(h)+\":\"+\"0\"+str(m) if m < 10 else str(h)+\":\"+str(m))\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                if bin(i).count(\"1\")+bin(j).count(\"1\") == turnedOn:\n",
    "                    res.append(str(i)+\":\"+'{:0>2d}'.format(j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        a=[]\n",
    "        min_a=[1,2,4,8,16,32,0,0,0,0]\n",
    "        hour_a=[0,0,0,0,0,0,1,2,4,8]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def BinTime(turnon,index,min_now,hour_now):\n",
    "            if min_now>59 or hour_now>11:\n",
    "                return\n",
    "            if turnon==turnedOn:\n",
    "                a.append(str(hour_now)+':'+'0'*(2-len(str(min_now)))+str(min_now))\n",
    "                if hour_now>10:\n",
    "                    print(str(hour_now)+':'+str(min_now))\n",
    "                return\n",
    "            for i in range(1,11-index):\n",
    "                BinTime(turnon+1,index+i,min_now+min_a[index+i-1],hour_now+hour_a[index+i-1])\n",
    "        BinTime(0,0,0,0)\n",
    "        return a\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        hours = [1,2,4,8,0,0,0,0,0,0]\n",
    "        munutes = [0,0,0,0,1,2,4,8,16,32]\n",
    "        res = []\n",
    "        def backtrack(turnedOn, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if turnedOn == 0:\n",
    "                res.append('%d:%02d' % (hour,minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(turnedOn-1, i+1, hour+hours[i], minute+munutes[i])\n",
    "        \n",
    "        backtrack(turnedOn, 0, 0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res = []\n",
    "        for minutes in range(720):\n",
    "            hour = minutes // 60\n",
    "            minute = minutes % 60\n",
    "            if bin(hour).count('1') + bin(minute).count('1') == turnedOn:\n",
    "                res.append(f'{hour}:0{minute}' if minute // 10 == 0 else f'{hour}:{minute}')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        hours = [1,2,4,8,0,0,0,0,0,0]\n",
    "        munutes = [0,0,0,0,1,2,4,8,16,32]\n",
    "        res = []\n",
    "        def backtrack(turnedOn, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if turnedOn == 0:\n",
    "                res.append('%d:%02d' % (hour,minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(turnedOn-1, i+1, hour+hours[i], minute+munutes[i])\n",
    "        \n",
    "        backtrack(turnedOn, 0, 0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f   # 用位运算取出高 4 位和低 6 位\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                   ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                if bin(i).count('1') + bin(j).count('1') == turnedOn:\n",
    "                    ans.append(str(i) + ':' + str(j).zfill(2))\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f   # 用位运算取出高 4 位和低 6 位\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count('1') + bin(m).count('1') == turnedOn:\n",
    "                    res.append(f\"{h}:{m:02d}\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        arr = [1,2,4,8,1,2,4,8,16,32]\n",
    "        ans = []\n",
    "\n",
    "        def dfs(i, j, h, m):\n",
    "            if i == len(arr):\n",
    "                if j == 0:\n",
    "                    # 小时（0-11），分钟（0-59）\n",
    "                    if h > 11 or m > 59:\n",
    "                        return \n",
    "                    if len(str(m)) == 1:\n",
    "                        m = '0' + str(m)\n",
    "                    ans.append(f'{h}:{m}')\n",
    "                return\n",
    "            # 选\n",
    "            if i <= 3:\n",
    "                dfs(i+1, j-1, h+arr[i], m)\n",
    "            else:\n",
    "                dfs(i+1, j-1, h, m+arr[i])\n",
    "            # 不选\n",
    "            dfs(i+1, j, h, m)\n",
    "        dfs(0, turnedOn, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        # 从0:00 -> 11:59遍历所有的可行解\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                # 若该时间所需点亮的灯与trunedOn相等，则符合\n",
    "                if bin(i).count('1') + bin(j).count('1') == turnedOn:\n",
    "                    ans.append(f\"{i}:{j:02d}\")  # 分钟需要保留2位整数\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                if bin(i).count('1') + bin(j).count('1') == turnedOn:  # 判断二进制位上有几个1\n",
    "                    res.append(f\"{i}:{j:02d}\")  # 02d表示输出为两位，不足的地方使用0补全\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans=[]\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                h_count = bin(h).count(\"1\")\n",
    "                m_count = bin(m).count(\"1\")\n",
    "\n",
    "                if h_count+m_count == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    if m < 10:\n",
    "                        ans.append(str(h)+\":\"+\"0\"+str(m))\n",
    "                    else:\n",
    "                        ans.append(str(h) + \":\" + str(m))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f   # 用位运算取出高 4 位和低 6 位\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                ans.append(\"{}:{:02d}\".format(h,m))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn):\n",
    "        result = []\n",
    "        if turnedOn >= 9:\n",
    "            return result\n",
    "        if turnedOn == 0:\n",
    "            result = [\"0:00\"]\n",
    "            return result\n",
    "\n",
    "        map_list = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4]\n",
    "        temp = {}\n",
    "        for i in range(60):\n",
    "            if map_list[i] in temp:\n",
    "                temp[map_list[i]].append(i)\n",
    "            else:\n",
    "                temp[map_list[i]] = [i]\n",
    "\n",
    "        for hour in range(turnedOn + 1):\n",
    "            if hour > 3:\n",
    "                break\n",
    "            minute = turnedOn - hour\n",
    "            if minute > 5:\n",
    "                continue\n",
    "            hour_list = [i for i in temp[hour] if i < 12]\n",
    "            minute_list = temp[minute]\n",
    "            for item1 in hour_list:\n",
    "                for item2 in minute_list:\n",
    "                    item2 = str(item2).zfill(2)\n",
    "                    result.append(f\"{int(item1)}:{str(item2)}\")\n",
    "        return result\n",
    "        # temp = [0]\n",
    "        # for i in range(1, 61):\n",
    "        #     temp.append(temp[i & (i - 1)] + 1)\n",
    "        # print(temp)\n",
    "        # result = []\n",
    "        # if turnedOn >= 9:\n",
    "        #     return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(1024):\n",
    "            h,m=i>>6,i&0x3f\n",
    "            if h<12 and m<60 and bin(i).count(\"1\")==turnedOn:\n",
    "                res.append(f\"{h}:{m:02d}\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        Dict=defaultdict(list)\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                x=i.bit_count()+j.bit_count()\n",
    "                Dict[x].append(str(i)+':'+str(j).zfill(2))\n",
    "        return Dict[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "#         ans = list()\n",
    "#         for i in range(1024):\n",
    "#             h, m = i >> 6, i & 0x3f   # 用位运算取出高 4 位和低 6 位\n",
    "#             if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "#                 ans.append(f\"{h}:{m:02d}\")\n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        # 枚举\n",
    "        ans = []\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count('1') + bin(m).count('1') == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        self.res = []\n",
    "        self.l = [8, 4, 2, 1, 32, 16, 8, 4, 2, 1]\n",
    "        self.backTrack(0, 0, 0, turnedOn)\n",
    "        return self.res\n",
    "    \n",
    "    def backTrack(self, index, hour, minute, num):\n",
    "        if hour > 11 or minute > 59:\n",
    "            return\n",
    "        if num == 0:\n",
    "            self.res.append(\"%d:%02d\" % (hour, minute))\n",
    "            return\n",
    "        for i in range(index, 10):\n",
    "            if i <= 3:\n",
    "                self.backTrack(i+1,hour + self.l[i], minute, num - 1)\n",
    "            else:\n",
    "                self.backTrack(i+1,hour, minute + self.l[i], num - 1)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        nums = [800, 400, 200, 100, 32, 16, 8, 4, 2, 1]\n",
    "        ans = []\n",
    "        for x in combinations(nums, turnedOn):\n",
    "            k = sum(x)\n",
    "            h, m = k // 100, k % 100\n",
    "            if h < 12 and m < 60:\n",
    "                ans.append(f'{h}:{str(m).rjust(2, \"0\")}')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                res.append(f\"{h}:{m:02d}\")\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\r\n",
    "        ans = list()\r\n",
    "        for h in range(12):\r\n",
    "            for m in range(60):\r\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\r\n",
    "                    ans.append(f\"{h}:{m:02d}\")\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, num: int) -> List[str]:\n",
    "        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]\n",
    "        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]\n",
    "        res = []\n",
    "        def backtrack(num, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if num == 0:\n",
    "                res.append('%d:%02d' % (hour, minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])\n",
    "        \n",
    "        backtrack(num, 0, 0, 0)\n",
    "        return res\n",
    "\n",
    "# num - 1: 在每次递归调用时，我们都减少一个LED灯的计数（表示我们已经选择了一个灯）。当 num 达到0时，意味着我们达到了所需的LED灯数量\n",
    "# i + 1: 这是控制函数递归不重复使用同一个LED灯的。我们传递 i + 1 来确保在下一轮递归中，我们从当前LED灯的下一个开始选择，防止重复\n",
    "# hour + hours[i]: 这里我们将当前小时数与 hours 数组中的第 i 个值相加，这是因为 hours 数组代表每个LED灯对小时数的贡献。由于这个数组已经预设了小时LED灯的值，我们只需要根据当前灯的索引增加小时数\n",
    "# minute + minutes[i]: 与小时数类似，这里我们将当前分钟数与 minutes 数组中的第 i 个值相加。minutes 数组代表每个LED灯对分钟数的贡献。这样可以累积当前已选择的灯对分钟数的总贡献\n",
    "\n",
    "# 递归终止条件是：\n",
    "# 当小时数超过11或者分钟数超过59时，这个时间不合法，递归返回。\n",
    "# 当达到了所需的LED灯数量（num 等于0），我们将当前的时间添加到结果 res 中。这里使用格式化字符串 '％d:%02d' ％ (hour, minute) 以正确的格式输出时间，确保分钟部分是两位数的表示"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "      ans=[]\n",
    "      h=[8,4,2,1]\n",
    "      minn=[32,16,8,4,2,1]\n",
    "      def f(x,t,step,num):\n",
    "        \n",
    "        nonlocal ans1\n",
    "        if num==0:\n",
    "          ans1.append('0')\n",
    "          return\n",
    "        if t>11:\n",
    "          return\n",
    "        if step==num:\n",
    "          ans1.append(str(t))\n",
    "          return\n",
    "        for j in range(x+1,4):\n",
    "          f(j,t+h[j],step+1,num)\n",
    "      def g(x,t,step,num):\n",
    "        nonlocal ans2\n",
    "        if num==0:\n",
    "          ans2.append('00')\n",
    "          return \n",
    "        if t>59:\n",
    "          return\n",
    "        if step==num:\n",
    "          if t<10:\n",
    "            ans2.append('0'+str(t))\n",
    "          else:\n",
    "            ans2.append(str(t))\n",
    "          return\n",
    "        for j in range(x+1,6):\n",
    "          g(j,t+minn[j],step+1,num)\n",
    "      for i in range(turnedOn+1):\n",
    "        if i<=4 and turnedOn-i<=6:\n",
    "          ans1=[]\n",
    "          ans2=[]\n",
    "          f(-1,0,0,i)\n",
    "          g(-1,0,0,turnedOn-i)\n",
    "          # print(i,ans1)\n",
    "          # print(turnedOn-i,ans2)\n",
    "          # print(\"====\")\n",
    "          for a1 in ans1:\n",
    "            for a2 in ans2:\n",
    "\n",
    "              ans.append(a1+\":\"+a2)\n",
    "      # ans1=[]\n",
    "      # ans2=[]\n",
    "      # f(-1,0,0,1)\n",
    "      # print(ans1)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, num: int) -> List[str]:\n",
    "        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]\n",
    "        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]\n",
    "        res = []\n",
    "        def backtrack(num, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if num == 0:\n",
    "                res.append('%d:%02d' % (hour, minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])\n",
    "        \n",
    "        backtrack(num, 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "H = (8, 4, 2, 1)\n",
    "M = (32, 16, 8, 4, 2, 1)\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        # h为H上亮的灯数，最多亮3个\n",
    "        for h in range(min(4, turnedOn + 1)):\n",
    "            # M上的灯最多亮5个\n",
    "            m = turnedOn - h\n",
    "            if not(0 <= m <= 5):\n",
    "                continue\n",
    "            for hour in map(sum, combinations(H, h)):\n",
    "                if hour < 12:\n",
    "                    for mini in map(sum, combinations(M, m)):\n",
    "                        if mini < 60:\n",
    "                            ans.append(f'{hour}:{mini:02}')\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        \n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, num: int) -> List[str]:\n",
    "        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]\n",
    "        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]\n",
    "        res = []\n",
    "        def backtrack(num, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if num == 0:\n",
    "                res.append('%d:%02d' % (hour, minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])\n",
    "        \n",
    "        backtrack(num, 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(0,12):\n",
    "            for j in range(0,60):\n",
    "                if bin(i).count('1')+bin(j).count('1')==turnedOn:\n",
    "                    res.append(f'{i}:{j:02d}')\n",
    "        return res             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 枚举，时间O(1)\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n",
    "    # 二进制枚举，时间O(1)\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f   # 用位运算取出高 4 位和低 6 位\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:  # 符合规则\n",
    "                ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "        \n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "\n",
    "    def readBinaryWatch(self, turnedOn):\n",
    "        \"\"\"\n",
    "        在打开turnenOn栈灯的情况下, 所有可能的时间组合        \n",
    "        Args:\n",
    "            thruedOn (int): 打开的灯数\n",
    "        returns (list[str]): 所有可能的组合\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if turnedOn == None or turnedOn == 0:\n",
    "            return ['0:00']\n",
    "        \n",
    "        self.process(0, turnedOn, 0, 0)\n",
    "        return self.ans \n",
    "    \n",
    "    \n",
    "    def process(self, index, left_k, h, m):\n",
    "        \"\"\"\n",
    "        表示\n",
    "        \n",
    "        \"\"\"\n",
    "        #递归出口, index == 10, 所有的灯都选择完毕, left_k == 0, 没有选择灯的次数了\n",
    "        if index == 10 or left_k == 0:\n",
    "            if left_k == 0:\n",
    "                #结果符合条件, 加入ans\n",
    "                if h <= 11 and m <= 59: #分钟必须是两位数'03', '00'\n",
    "                    m_str = str(m)\n",
    "                    if len(m_str) < 2:\n",
    "                        m_str = '0' + m_str\n",
    "                    self.ans.append(str(h) + ':' + m_str)\n",
    "            return \n",
    "        #         小时               分钟 \n",
    "        #[8, 4, 2, 1, 32, 16, 8, 4, 2, 1]   为简化运算, 将10栈灯映射在该数组上\n",
    "        #case1.选择当前字符\n",
    "        if 0 <= index <= 3:\n",
    "            temp_h = 2**(3 - index)\n",
    "            if h + temp_h <= 11:\n",
    "                self.process(index + 1, left_k - 1, h + temp_h, m)\n",
    "        else:\n",
    "            temp_m = 2**(9 - index)\n",
    "            if m + temp_m <= 59:\n",
    "                self.process(index + 1, left_k - 1, h, m + temp_m)\n",
    "\n",
    "        #case2.不选择当前字符, 直接跳过\n",
    "        self.process(index + 1, left_k, h, m)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        h_count = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3]\n",
    "        m_count = [\n",
    "            0,\n",
    "            1,\n",
    "            1, 2,\n",
    "            1, 2, 2, 3,\n",
    "            1, 2, 2, 3, 2, 3, 3, 4,\n",
    "            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,\n",
    "            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,\n",
    "        ]\n",
    "\n",
    "        ans = []\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                if h_count[i] + m_count[j] == turnedOn:\n",
    "                    ans.append(str(i) + \":\" + \"%02d\" % (j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(12):\n",
    "            for j in range(60):\n",
    "                if bin(i).count('1') + bin(j).count('1') == turnedOn:\n",
    "                    if j >= 10:\n",
    "                        res.append(str(i) + ':' + str(j))\n",
    "                    elif j < 10:\n",
    "                        res.append(str(i) + ':0' + str(j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getCnt(x):\n",
    "    ans, i = 0, x\n",
    "    while i > 0:\n",
    "        ans += 1\n",
    "        i -= lowbit(i)\n",
    "    return ans\n",
    "    \n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "map = defaultdict(list)\n",
    "for h in range(12):\n",
    "    for m in range(60):\n",
    "        tot = getCnt(h) + getCnt(m)\n",
    "        map[tot].append(f\"{h}:{m:02d}\")\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        return map[turnedOn]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def readBinaryWatch(self,turnedOn):\r\n",
    "        def backtrack(leds, start, count):\r\n",
    "            if count == turnedOn:\r\n",
    "                hour = leds >> 6\r\n",
    "                minute = leds & 0b111111\r\n",
    "                if hour < 12 and minute < 60:\r\n",
    "                    time = f\"{hour}:{minute:02}\"\r\n",
    "                    output.append(time)\r\n",
    "                return\r\n",
    "            \r\n",
    "            for i in range(start, 10):\r\n",
    "                backtrack(leds | (1 << i), i + 1, count + 1)\r\n",
    "        \r\n",
    "        output = []\r\n",
    "        backtrack(0, 0, 0)\r\n",
    "        return output\r\n",
    "\r\n",
    "# [\"0:03\",\"0:05\",\"0:06\",\"0:09\",\"0:10\",\"0:12\",\"0:17\",\"0:18\",\"0:20\",\"0:24\",\"0:33\",\"0:34\",\"0:36\",\"0:40\",\"0:48\",\"1:01\",\"1:02\",\"1:04\",\"1:08\",\"1:16\",\"1:32\",\"2:01\",\"2:02\",\"2:04\",\"2:08\",\"2:16\",\"2:32\",\"3:00\",\"4:01\",\"4:02\",\"4:04\",\"4:08\",\"4:16\",\"4:32\",\"5:00\",\"6:00\",\"8:01\",\"8:02\",\"8:04\",\"8:08\",\"8:16\",\"8:32\",\"9:00\",\"10:00\"]       \r\n",
    "# [\"0:48\",\"8:32\",\"8:16\",\"8:08\",\"8:04\",\"8:02\",\"8:01\",\"4:32\",\"4:16\",\"4:08\",\"4:04\",\"4:02\",\"4:01\",\"2:32\",\"2:16\",\"2:08\",\"2:04\",\"2:02\",\"2:01\",\"1:32\",\"1:16\",\"1:08\",\"1:04\",\"1:02\",\"1:01\",\"10:00\",\"9:00\",\"6:00\",\"5:00\",\"3:00\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(1024):\n",
    "            h, m = i >> 6, i & 0x3f\n",
    "            if h < 12 and m < 60 and bin(i).count(\"1\") == turnedOn:\n",
    "                res.append(f\"{h}:{m:02d}\")\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "H = (8, 4, 2, 1)\n",
    "M = (32, 16, 8, 4, 2, 1)\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        # h为H上亮的灯数，最多亮3个\n",
    "        for h in range(min(4, turnedOn + 1)):\n",
    "            # M上的灯最多亮5个\n",
    "            m = turnedOn - h\n",
    "            if not(0 <= m <= 5):\n",
    "                continue\n",
    "            for hour in map(sum, combinations(H, h)):\n",
    "                if hour < 12:\n",
    "                    for mini in map(sum, combinations(M, m)):\n",
    "                        if mini < 60:\n",
    "                            ans.append(f'{hour}:{mini:02}')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self,n: int) -> List[str]:\n",
    "        return [str(h)+':'+'0'*(m<10)+str(m) for h in range(12) for m in range(60) if (bin(m)  +bin(h)). count('1') == n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "H = (8, 4, 2, 1)\n",
    "M = (32, 16, 8, 4, 2, 1)\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "        for h in range(min(4, turnedOn + 1)):\n",
    "            # i为H上亮的灯数，最多亮3个\n",
    "            # M上的灯为0-5才合法\n",
    "            m = turnedOn - h\n",
    "            if not(0 <= m <= 5):\n",
    "                continue\n",
    "            for hour in map(sum, combinations(H, h)):\n",
    "                for mini in map(sum, combinations(M, m)):\n",
    "                    if mini < 60 and hour < 12:\n",
    "                        ans.append(f'{hour}:{mini:02}')\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def get_num_bin_1_cnt(num: int) -> int:\n",
    "            ans = 0\n",
    "            while num > 0:\n",
    "                ans = ans + (num & 1)\n",
    "                num >>= 1\n",
    "            return ans\n",
    "\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if get_num_bin_1_cnt(h) + get_num_bin_1_cnt(m) == turnedOn:\n",
    "                    if m < 10: m = '0' + str(m)\n",
    "                    ans.append(\"{}:{}\".format(h, m))\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.result_all = None\n",
    "        self.nums = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32]\n",
    "        self.visited = None\n",
    "    \n",
    "    def readBinaryWatch(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.result_all = []\n",
    "        self.visited = [0 for _ in range(len(self.nums))]\n",
    "        self.dfs(num, 0, 0)\n",
    "        return self.result_all\n",
    "    \n",
    "    def dfs(self, num, step, start):\n",
    "        if step == num:\n",
    "            self.result_all.append(self.handle_date(self.visited))\n",
    "            return\n",
    "        for i in range(start, len(self.nums)):\n",
    "            self.visited[i] = 1\n",
    "            if not self.calc_sum(self.visited):\n",
    "                self.visited[i] = 0\n",
    "                continue\n",
    "            self.dfs(num, step + 1, i + 1)\n",
    "            self.visited[i] = 0\n",
    "        return\n",
    "            \n",
    "    def calc_sum(self, visited):\n",
    "        sum_h = 0\n",
    "        sum_m = 0\n",
    "        for i in range(len(visited)):\n",
    "            if visited[i] == 0:\n",
    "                continue\n",
    "            if i < 4:\n",
    "                sum_h += self.nums[i]\n",
    "            else:\n",
    "                sum_m += self.nums[i]\n",
    "        return 0 <= sum_h <= 11 and 0 <= sum_m <= 59\n",
    "    \n",
    "    def handle_date(self, visited):\n",
    "        sum_h = 0\n",
    "        sum_m = 0\n",
    "        for i in range(len(visited)):\n",
    "            if visited[i] == 0:\n",
    "                continue\n",
    "            if i < 4:\n",
    "                sum_h += self.nums[i]\n",
    "            else:\n",
    "                sum_m += self.nums[i]\n",
    "        result = \"\" + str(sum_h) + \":\"\n",
    "        if sum_m < 10:\n",
    "            result += \"0\" + str(sum_m)\n",
    "        else:\n",
    "            result += str(sum_m)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        ans = list()\n",
    "        for h in range(12):\n",
    "            for m in range(60):\n",
    "                if bin(h).count(\"1\") + bin(m).count(\"1\") == turnedOn:\n",
    "                    ans.append(f\"{h}:{m:02d}\")\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, num: int) -> List[str]:\n",
    "        #copy\n",
    "        hours = [1,2,4,8,0,0,0,0,0,0]\n",
    "        minutes = [0,0,0,0,1,2,4,8,16,32]\n",
    "        res = []\n",
    "        def backtrack(num,index,hour,minute):\n",
    "            if hour >11 or minute >59:\n",
    "                return\n",
    "            if num == 0:\n",
    "                res.append('%d:%02d'%(hour,minute))\n",
    "                return \n",
    "            for i in range(index,10):\n",
    "                backtrack(num-1,i+1,hour+hours[i],minute+minutes[i])\n",
    "        \n",
    "        backtrack(num,0,0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        result = set()\n",
    "        h_dict = [8,4,2,1]\n",
    "        m_dict = [32,16,8,4,2,1]\n",
    "        def branch(cur_on, cur_h, cur_m, cur_h_idx, cur_m_idx):\n",
    "            if cur_on == 0:\n",
    "                h = str(cur_h)\n",
    "                m = str(cur_m)\n",
    "                if len(m) == 1:\n",
    "                    m = '0' + m\n",
    "                r = h + ':' + m\n",
    "                if not r in result:\n",
    "                    result.add(r)\n",
    "            else:\n",
    "                if cur_h_idx < 4:\n",
    "                    if cur_h + h_dict[cur_h_idx] < 12:\n",
    "                        branch(cur_on - 1, cur_h + h_dict[cur_h_idx], cur_m, cur_h_idx+1, cur_m_idx)\n",
    "                    branch(cur_on, cur_h, cur_m, cur_h_idx+1, cur_m_idx)\n",
    "                if cur_m_idx < 6:\n",
    "                    if cur_m + m_dict[cur_m_idx] < 60:\n",
    "                        branch(cur_on - 1, cur_h, cur_m + m_dict[cur_m_idx], cur_h_idx, cur_m_idx+1)\n",
    "                    branch(cur_on, cur_h, cur_m, cur_h_idx, cur_m_idx+1)\n",
    "        \n",
    "        branch(turnedOn, 0, 0, 0, 0)\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        def k(onenum,index,standnum,ans,cur):\n",
    "            if index==standnum:\n",
    "                if onenum==0:\n",
    "                    cur=int(cur,2)\n",
    "                    if standnum==4:\n",
    "                        if cur<=11:\n",
    "                            ans.append(cur)\n",
    "                    elif standnum==6:\n",
    "                        if cur<=59:\n",
    "                            ans.append(cur)\n",
    "                return True\n",
    "            k(onenum-1,index+1,standnum,ans,cur+'1')\n",
    "            k(onenum,index+1,standnum,ans,cur+'0')\n",
    "\n",
    "\n",
    "        def d(upperlight,bottomlight):\n",
    "            upperarr=[]\n",
    "            k(upperlight,0,4,upperarr,'')\n",
    "            bottomarr=[]\n",
    "            k(bottomlight,0,6,bottomarr,'')\n",
    "            ans=[]\n",
    "            for i in upperarr:\n",
    "                for j in bottomarr:\n",
    "                    pre=str(i)\n",
    "                    post=str(j)\n",
    "                    post=post.rjust(2,'0')\n",
    "                    ans.append(pre+':'+post)\n",
    "            return ans\n",
    "\n",
    "        def f(restlight,upperlight,bottomlight,ans):\n",
    "            if upperlight>3 or bottomlight>5:\n",
    "                return False\n",
    "            if restlight==0:\n",
    "                ans.extend(d(upperlight,bottomlight))\n",
    "                return True\n",
    "            f(restlight-1,upperlight+1,bottomlight,ans)\n",
    "            f(restlight-1,upperlight,bottomlight+1,ans)\n",
    "        ans=[]\n",
    "        f(turnedOn,0,0,ans)\n",
    "        return list(set(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def readBinaryWatch_H(self,n)->list[int]:\r\n",
    "        H=[8,4,2,1]\r\n",
    "        if n==1:return H\r\n",
    "        elif n==0:return [0]\r\n",
    "        elif n==2:return [10,9,6,5,3]\r\n",
    "        elif n==3:return [11,7]\r\n",
    "        else:return []\r\n",
    "        \r\n",
    "    def readBinaryWatch_M(self,n)->list[int]:\r\n",
    "        H=[32,16,8,4,2,1]\r\n",
    "        output=[]\r\n",
    "        if n==0:return [0]\r\n",
    "        elif n==1:return H\r\n",
    "        elif n==2:\r\n",
    "            for i in range(5):\r\n",
    "                for j in range(i+1,6):\r\n",
    "                    total=H[i]+H[j]\r\n",
    "                    if (total in output) or total>59:continue\r\n",
    "                    output.append(total)\r\n",
    "            return output\r\n",
    "        elif n==3:\r\n",
    "            for i in range(4):\r\n",
    "                for j in range(i+1,5):\r\n",
    "                    for k in range(j+1,6):\r\n",
    "                        total=H[i]+H[j]+H[k]\r\n",
    "                        if (total in output) or total>59:continue\r\n",
    "                        output.append(total)\r\n",
    "            return output\r\n",
    "        elif n==4:\r\n",
    "            for i in range(5):\r\n",
    "                for j in range(i+1,6):\r\n",
    "                    total=63-H[i]-H[j]\r\n",
    "                    if (total in output) or total>59:continue\r\n",
    "                    output.append(total)\r\n",
    "            return output\r\n",
    "        elif n==5:return[31,47,55,59]\r\n",
    "        else: return []\r\n",
    "                        \r\n",
    "            \r\n",
    "    def get_output(self,H,M):\r\n",
    "        output=[]\r\n",
    "        for hour in H:\r\n",
    "            for minute in M:\r\n",
    "                output.append(str(hour)+\":\"+str(minute).zfill(2))\r\n",
    "        return output\r\n",
    "            \r\n",
    "            \r\n",
    "    def readBinaryWatch(self,turnedOn: int) -> list[str]:\r\n",
    "        H=[]\r\n",
    "        M=[]\r\n",
    "        output=[]\r\n",
    "        if turnedOn==0:return [\"0:00\"]\r\n",
    "        elif turnedOn==1:\r\n",
    "            H=self.readBinaryWatch_H(0)\r\n",
    "            M=self.readBinaryWatch_M(1)\r\n",
    "            output.extend(self.get_output(H,M))\r\n",
    "            H=self.readBinaryWatch_H(1)\r\n",
    "            M=self.readBinaryWatch_M(0)\r\n",
    "            output.extend(self.get_output(H,M))\r\n",
    "            return output\r\n",
    "        else:\r\n",
    "            for i in range(turnedOn+1):\r\n",
    "                if i < 4 and turnedOn-i<6:\r\n",
    "                    H=self.readBinaryWatch_H(i)\r\n",
    "                    M=self.readBinaryWatch_M(turnedOn-i)\r\n",
    "                    print(M)\r\n",
    "                    output.extend(self.get_output(H,M))\r\n",
    "        return output\r\n",
    "# [\"0:03\",\"0:05\",\"0:06\",\"0:09\",\"0:10\",\"0:12\",\"0:17\",\"0:18\",\"0:20\",\"0:24\",\"0:33\",\"0:34\",\"0:36\",\"0:40\",\"0:48\",\"1:01\",\"1:02\",\"1:04\",\"1:08\",\"1:16\",\"1:32\",\"2:01\",\"2:02\",\"2:04\",\"2:08\",\"2:16\",\"2:32\",\"3:00\",\"4:01\",\"4:02\",\"4:04\",\"4:08\",\"4:16\",\"4:32\",\"5:00\",\"6:00\",\"8:01\",\"8:02\",\"8:04\",\"8:08\",\"8:16\",\"8:32\",\"9:00\",\"10:00\"]       \r\n",
    "# [\"0:48\",\"8:32\",\"8:16\",\"8:08\",\"8:04\",\"8:02\",\"8:01\",\"4:32\",\"4:16\",\"4:08\",\"4:04\",\"4:02\",\"4:01\",\"2:32\",\"2:16\",\"2:08\",\"2:04\",\"2:02\",\"2:01\",\"1:32\",\"1:16\",\"1:08\",\"1:04\",\"1:02\",\"1:01\",\"10:00\",\"9:00\",\"6:00\",\"5:00\",\"3:00\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        #1、灯的数量拆分  \n",
    "        def nums(turnedOn: int) -> List[int]:\n",
    "            Hmax,Mmax=3,5\n",
    "            res=[]\n",
    "            if turnedOn>Hmax+Mmax:\n",
    "                return res\n",
    "            for i in range(min(Hmax,turnedOn)+1):\n",
    "                if turnedOn-i<=Mmax:\n",
    "                    res.append([i,turnedOn-i])\n",
    "            return res\n",
    "\n",
    "        \n",
    "        #3、灯的位置转换成数字\n",
    "        \n",
    "        Hlist=[1,2,4,8]\n",
    "        Mlist=[1,2,4,8,16,32]\n",
    "        \n",
    "        res=[]\n",
    "        n_nums = nums(turnedOn)\n",
    "        if not n_nums:\n",
    "            return res\n",
    "        for i in n_nums:\n",
    "            hh_res=[]\n",
    "            mm_res=[]\n",
    "            #2、灯出现的位置，排列组合\n",
    "            #print(i)\n",
    "            comH = list(combinations(Hlist,i[0]))\n",
    "            comM = list(combinations(Mlist,i[1]))\n",
    "            for j in comH:\n",
    "                hh=0\n",
    "                for k in j:\n",
    "                    hh+=k\n",
    "                if hh<12:\n",
    "                    hh_res.append(hh)\n",
    "            for j in comM:\n",
    "                mm=0\n",
    "                for k in j:\n",
    "                    mm+=k\n",
    "                if mm<60:\n",
    "                    mm_res.append(mm)\n",
    "        \n",
    "\n",
    "            for i in hh_res:\n",
    "                for j in mm_res:\n",
    "                    k=str(i)\n",
    "                    if j <10:\n",
    "                        g='0'+str(j)\n",
    "                    else:\n",
    "                        g=str(j)\n",
    "                    res.append(k+':'+g)\n",
    "        \n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, num: int) -> List[str]:\n",
    "        hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]\n",
    "        minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]\n",
    "        res = []\n",
    "        def backtrack(num, index, hour, minute):\n",
    "            if hour > 11 or minute > 59:\n",
    "                return\n",
    "            if num == 0:\n",
    "                res.append('%d:%02d' % (hour, minute))\n",
    "                return\n",
    "            for i in range(index, 10):\n",
    "                backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])\n",
    "        \n",
    "        backtrack(num, 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        H = {'0':0, '1':1, '2':1, '3':2, '4':1, '5':2, '6':2, '7':3, '8':1, '9':2, '10':2, '11':3}\n",
    "        M = {   0:['00'], \n",
    "                1:['01','02','04','08','16','32'],\n",
    "                2:['03','05','06','09','10','12','17','18','20','24','33','34','36','40','48'],\n",
    "                3:['07','11','13','14','19','21','22','25','26','28','35','37','38','41','42','44','49','50','52','56'],\n",
    "                4:['15','23','27','29','30','39','43','45','46','51','53','54','57','58'],\n",
    "                5:['31','47','55','59']\n",
    "            }\n",
    "\n",
    "        res = []\n",
    "        if (turnedOn >= 9):\n",
    "            return res\n",
    "\n",
    "        for a in H.keys():\n",
    "            h = H[a]\n",
    "            m = turnedOn - h\n",
    "            if (m < 0 or m > 5):\n",
    "                continue\n",
    "            for b in M[m]:\n",
    "                res.append(a+\":\"+b)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def readBinaryWatch(self, turnedOn: int) -> List[str]:\n",
    "        if turnedOn >= 9 or turnedOn < 0:\n",
    "            return []\n",
    "        if turnedOn == 0:\n",
    "            return [\"0:00\"]\n",
    "        else:\n",
    "            ans = []\n",
    "            h_dict = self.get_h()\n",
    "            m_dict = self.get_m()\n",
    "            for i in range(turnedOn+1):\n",
    "                h_list = h_dict.get(str(i), [])\n",
    "                m_list = m_dict.get(str(turnedOn - i), [])\n",
    "                if len(h_list) > 0 and len(m_list) > 0:\n",
    "                    for h in h_list:\n",
    "                        for m in m_list:\n",
    "                            ans.append(h + \":\" + m)\n",
    "                else:\n",
    "                    continue\n",
    "            return ans\n",
    "\n",
    "    def get_h(self):\n",
    "        map_dict = {}\n",
    "        for i in range(12):\n",
    "            tmp = i\n",
    "            ans = bin(tmp).count(\"1\")\n",
    "            if str(ans) not in map_dict:\n",
    "                map_dict[str(ans)] = [str(i)]\n",
    "            else:\n",
    "                map_dict[str(ans)].append(str(i))\n",
    "        return map_dict\n",
    "    \n",
    "    def get_m(self):\n",
    "        map_dict = {}\n",
    "        for i in range(60):\n",
    "            tmp = i\n",
    "            ans = bin(tmp).count(\"1\")\n",
    "            if str(ans) not in map_dict:\n",
    "                if i < 10:\n",
    "                    map_dict[str(ans)] = [\"0\" + str(i)]\n",
    "                else:\n",
    "                    map_dict[str(ans)] = [str(i)]\n",
    "            else:\n",
    "                if i < 10:\n",
    "                    map_dict[str(ans)].append(\"0\" + str(i))\n",
    "                else:\n",
    "                    map_dict[str(ans)].append(str(i))\n",
    "        return map_dict\n",
    "            \n",
    "\n",
    "# if __name__ == \"__main__\":\n",
    "#     solution = Solution()\n",
    "#     print(solution.get_h())\n",
    "#     print(solution.get_m())\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
